package 链表;

import java.util.HashSet;
import java.util.Set;

public class No82删除排序链表中的重复元素_2 {

    /**
     * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
     *
     * 示例 1:
     * 输入: 1->2->3->3->4->4->5
     * 输出: 1->2->5
     * 示例 2:
     * 输入: 1->1->1->2->3
     * 输出: 2->3
     */

    static Set<Integer> set=new HashSet<>();
    static Set<Integer> set1=new HashSet<>();

    public static ListNode deleteDuplicates(ListNode head) {

        ListNode listNode=new ListNode();
        listNode.next=head;
        ListNode cur=listNode.next;
        ListNode op=listNode;

        /**
         * 没重复的话需要保存本次没重复的cur,
         * 若下一次有重复的了,那么就会进行删除(知道了重复,那不就是要保存两个cur)
         */
        while (cur!=null){

            if(set.contains(cur.val)){
                set1.add(cur.val);//防止重复出现val,后面再遍历一次
                //重复了,就开始删除操作
                op.next=cur.next;//抛弃此节点
                cur.next=null;
                cur=op.next;//重新拼接上
            }else{
                //没重复就跑往下一个,需要保存什么呢?
                op=cur;//保存本次节点
                set.add(cur.val);
                cur=cur.next;
            }

            //可以就先用这个来
            /*最后再进行set遍历,重新处理链表?*/
        }
        cur=listNode.next;
        op=listNode;
        while (cur!=null){
            if(set1.contains(cur.val)){
                //再次遍历,得到重复的
                op.next=cur.next;
                cur=op.next;
            }else{
                op=cur;
                cur=cur.next;
            }
        }

        return listNode.next;
    }

    /**
     * 快慢指针法
     * 慢:指向虚拟节点
     * 快:指向头节点
     * 一个while遍历整个链表,while里面的小while遍历fast和fast.next是否相同,相同就fast=fast.next
     * 小while出来后,就判断slow.next指针是否等于fast,如果等于说明没有被替换,就slow=slow.next
     * 如果不等于,则被替换了,那么slow.next指针就要指向fast.next
     */
    public static ListNode deleteDuplicatesGood1(ListNode head) {

        //先定义两个指针,一个快的,一个慢的;
        //快的去检索,慢的当作前驱指针
        ListNode listNode=new ListNode();
        listNode.next=head;

        ListNode slow=listNode;
        ListNode fast=listNode.next;

        //然后就开始遍历链表

        while (fast!=null){

//            boolean flag=false;
            //这里判断快指针有没有相同元素
            while (fast.next!=null&&fast.val==fast.next.val){
                //有相同元素,就一路删除下去
//                flag=true;
                fast=fast.next;
            }
            //删除完之后就剩下了一个fast元素,让慢指针指向fast.next即可
            //但是这里可能不是目标元素,所以加个判断
            if(slow.next!=fast)
                slow.next=fast.next;
            else
                slow=slow.next;

            fast=fast.next;
        }

        return listNode.next;
    }

    /**
     * 递归方法
     * 思路和上一个方法一样,递归返回什么呢?就是重复元素的第一个元素,然后让父元素.next等于目标.next
     */
    public static ListNode deleteDuplicatesGood2(ListNode head) {

        if(head==null)
            return null;

        if(head.next!=null&&head.val==head.next.val){

            //有重复元素
            /**
             * 没有next连接是关键,无next就是删除
             * 所有题解,删除重复的关键就在于这个while
             */
            while (head.next != null && head.val == head.next.val) {
                head = head.next;
            }


            return deleteDuplicatesGood2(head.next);
        }else{
            //没有重复元素||重复元素已经到底
            //传来的head可能是1.不是重复元素 2.重复元素已经到底了
            head.next=deleteDuplicatesGood2(head.next);
        }
        return head;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3,3,3,4,4,5};
        ListNode listNode = ListNode.createListNode(arr);
        ListNode result = deleteDuplicatesGood2(listNode);
        ListNode.printListNode(result);
    }

}
